package leetcode101.search_problem.dfs;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code2
 * @Description 547. Number of Provinces
 * There are n cities. Some of them are connected, while some are not.
 * If city a is connected directly with city b, and city b is connected directly with city c,
 * then city a is connected indirectly with city c.
 *
 * A province is a group of directly or indirectly connected cities and no other cities outside of the group.
 *
 * You are given an n x n matrix isConnected where isConnected[i][j] = 1
 * if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.
 *
 * Return the total number of provinces.
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-30 17:39
 */
public class Code2 {

    public static void main(String[] args) {
        int[][] matrix = new int[][] {{1,0,0,1},{0,1,1,0},{0,1,1,1},{1,0,1,1}};
//        int[][] matrix = new int[][] {{1, 1, 0},{1,1,0},{0,0,1}};
        System.out.println(findCircleNum(matrix));
    }

    public static int findCircleNum(int[][] isConnected) {
        int res = 0;
        for (int i = 0; i < isConnected.length; i++) {
            for (int j = 0; j < isConnected[i].length; j++) {
                if (isConnected[i][j] == 1) {
                    // 只要找到1 说明有一个新的省
                    res++;
                    dfs(isConnected, i);
                }
            }
        }
        return res;
    }

    public static void dfs(int[][] matrix, int i) {
        // 对于当前元素所在行，遇到一个1就把当前元素及其对角元素均置为0，然后去dfs当前元素所在列的那一行，即和该元素相邻元素的那一行
        for (int j = 0; j < matrix[i].length; j++) {
            if (matrix[i][j] == 1) {
                matrix[i][j] = 0;
                matrix[j][i] = 0;
                dfs(matrix, j);
            }
        }
    }
}

/*
这道题与第一题不同，这道题给的矩阵中每一个元素代表的是对应行列是否相连
 */